/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package yinshi.util;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
import java.util.Objects;
import java.util.Set;
import java.util.Stack;

/**
 * Graph class by which you can build a directional graph.
 *
 * @author yinshi
 */
public final class Graph {

    private final HashMap<Object, Node> nodes = new HashMap();
    private boolean fixed = false;

    /**
     * If the graph is fixed, the content can not be modified.
     *
     * @return true if the graph is fixed
     */
    public boolean isFixed() {
        return fixed;
    }

    /**
     * Fix the graph so that it can not be modified.
     *
     * @return true if the graph is fixed
     */
    public synchronized void fix() {
        for (Node node : nodes.values()) {
            node.in_links.trimToSize();
            node.out_links.trimToSize();
        }
        this.fixed = true;
    }

    /**
     * Put new node into the graph which can be accessed through the key. The
     * keys in the graph should be distinguishable by equals().
     *
     * @param key the key of the node.
     * @return the new node which is added into the graph.
     * @throws UnsupportedOperationException if the graph is fixed.
     * @throws NullPointerException if the key is null.
     * @throws IllegalArgumentException if the key already exists.
     */
    public synchronized Node addNode(Object key) {
        if (fixed) {
            throw new UnsupportedOperationException();
        }

        Objects.requireNonNull(key);
        if (nodes.containsKey(key)) {
            throw new IllegalArgumentException("key already exists");
        }

        Node node = new Node(this, key);
        nodes.put(key, node);
        return node;
    }

    /**
     * Get the node in the graph according to the key.
     *
     * @param key the key of the node.
     * @return the node which is associated with the key. If the node is not
     * found, null will be returned.
     * @throws NullPointerException if the key is null.
     */
    public Node getNode(Object key) {
        Objects.requireNonNull(key);
        if (!nodes.containsKey(key)) {
            return null;
        }
        return nodes.get(key);
    }

    /**
     * Remove the node according to the key. If there is no node associated with
     * key, nothing will be done.
     *
     * @param key the key.
     * @throws UnsupportedOperationException if the graph is fixed.
     * @throws NullPointerException if the key is null.
     */
    public synchronized void removeNode(Object key) {
        if (fixed) {
            throw new UnsupportedOperationException();
        }
        Objects.requireNonNull(key);
        Node node = nodes.get(key);
        if (node == null) {
            return;
        }
        node.removeAllLinks();
        node.removeAllInLinks();
        node.graph = null;
        nodes.remove(key);
    }

    /**
     * Return true if the graph contains the node which is indicated by the key.
     *
     * @param key the key.
     * @return NullPointerException if the key is null.
     */
    public boolean containsNode(Object key) {
        Objects.requireNonNull(key);
        return nodes.containsKey(key);
    }

    /**
     * Clear all the nodes in the graph.
     *
     * @throws UnsupportedOperationException if the graph is fixed.
     */
    public synchronized void clearNodes() {
        if (fixed) {
            throw new UnsupportedOperationException();
        }
        for (Node node : nodes.values()) {
            node.removeAllLinks();
            node.removeAllInLinks();
            node.graph = null;
        }
        nodes.clear();
    }

    /**
     * Return all the keys in the graph.
     *
     * @return the set of all the keys in the graph
     */
    public Set<Object> keySet() {
        return nodes.keySet();
    }

    /**
     * Return a string which represents the graph.
     *
     * @return the string.
     */
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("Graphics: ").append(super.toString()).append("\n");
        for (Map.Entry<Object, Node> entry : nodes.entrySet()) {
            sb.append("  Node: ").append(entry.getKey()).append("\n");
            for (Link link : entry.getValue().out_links) {
                sb.append("    Link to: ").append(link.targetNode.key).append("\n");
            }
            for (Link link : entry.getValue().in_links) {
                sb.append("    Linked from: ").append(link.originNode.key).append("\n");
            }
        }
        return sb.toString();
    }

    public void traverse(Object start, Handler handler) {
        Object key = start;
        Node node = getNode(start);
        out_loop:
        while (true) {
            for (int index = 0; index < node.out_links.size(); index++) {
                Link link = node.out_links.get(index);
                if (handler.judge(key, node, index, link)) {
                    key = link.targetNode.key;
                    node = link.targetNode;
                    continue out_loop;
                }
            }
            break out_loop;
        }
    }

    public void traverse(Object start, Handler handler, Listener listener) {
        Object key = start;
        Node node = getNode(start);

        out_loop:
        while (true) {
            for (int index = 0; index < node.out_links.size(); index++) {
                Link link = node.out_links.get(index);
                if (handler.judge(key, node, index, link)) {
                    boolean result = listener.move(key, node, index, link);
                    if (!result) {
                        return;
                    }
                    key = link.targetNode.key;
                    node = link.targetNode;
                    continue out_loop;
                }
            }
            break out_loop;
        }
    }

    public void traverse(Object start) {
        traverse(start, new Listener() {
            public boolean move(Object originKey, Node originNode, int link_index, Link link) {
                System.out.format("move from %s to %s\n", originKey, link.getTarget().getKey());
                return true;
            }
        });
    }

    public void traverse(Object start, Listener listener) {

        for (Node node : nodes.values()) {
            node.max_index = 0;
        }

        Node node = getNode(start);
        Stack<Node> stack = new Stack<>();
        stack.add(node);

        while (true) {
            if (stack.size() == 0) {
                break;
            }
            node = stack.peek();

            if (node.max_index < node.out_links.size()) {
                boolean result = listener.move(node.key, node, node.max_index, node.out_links.get(node.max_index));
                if (!result) {
                    return;
                }
                stack.push(node.out_links.get(node.max_index).targetNode);
                node.max_index++;
            } else {
                stack.pop();
            }
        }
    }

    /**
     * Get the collection of all the nodes in the graph.
     *
     * @return the collection of the nodes
     */
    public java.util.Collection<Node> getNodes() {
        return nodes.values();
    }

    public static class Node {

        private final ArrayList<Link> in_links = new ArrayList();
        private final ArrayList<Link> out_links = new ArrayList();
        private Graph graph;
        private Object key;
        private Object data;
        private int max_index;

        private Node(Graph graph, Object key) {
            this.graph = graph;
            this.key = key;
        }

        /**
         * Get the key related with this node in the graph
         *
         * @return the related key.
         */
        public Object getKey() {
            return key;
        }

        /**
         * Construct a new link from this node to the one which is indicated by
         * the key.
         *
         * @param key the key relating to the node which will be linked to.
         * @return the link which presents the relation. If the node cannot be
         * found, null will be returned.
         * @throws UnsupportedOperationException if the graph is fixed.
         */
        public Link linkTo(Object key) {
            synchronized (graph) {
                if (graph.fixed) {
                    throw new UnsupportedOperationException();
                }

                Node targetNode = graph.getNode(key);
                if (targetNode == null) {
                    return null;
                }
                Link link = new Link(this.graph, this, targetNode);
                out_links.add(link);
                targetNode.in_links.add(link);
                return link;
            }
        }

        /**
         * Remove the link which is indicated by the index in this node. The
         * index should be in the range of 0 to numOfLinks (excluded).
         *
         * @param index the index of the link in this node.
         * @throws UnsupportedOperationException if the graph is fixed.
         * @throws IndexOutOfBoundsException if the index is out of the range.
         */
        public void removeLink(int index) {
            synchronized (graph) {
                if (graph.fixed) {
                    throw new UnsupportedOperationException();
                }

                Link link = out_links.get(index);
                Node targetNode = link.targetNode;
                targetNode.in_links.remove(link);
                out_links.remove(index);
                link.graph = null;
                link.originNode = null;
                link.targetNode = null;
            }
        }

        /**
         * Remove all the links from this node.
         *
         * @throws UnsupportedOperationException if the graph is fixed.
         */
        public void removeAllLinks() {
            synchronized (graph) {
                if (graph.fixed) {
                    throw new UnsupportedOperationException();
                }

                for (Link link : out_links) {
                    Node targetNode = link.targetNode;
                    targetNode.in_links.remove(link);
                    link.graph = null;
                    link.originNode = null;
                    link.targetNode = null;
                }
                out_links.clear();
            }
        }

        /**
         * Return the number of the links in this node.
         *
         * @return the number of the links in this node.
         */
        public int numOfLinks() {
            return out_links.size();
        }

        /**
         * Get the link which is indicated by the index in this node. The index
         * should be in the range of 0 to numOfLinks (excluded).
         *
         * @param index the index of the link in this node.
         * @return the link.
         * @throws IndexOutOfBoundsException if the index is out of the range.
         */
        public Link getLink(int index) {
            return out_links.get(index);
        }

        /**
         * Get all the links in this node.
         *
         * @return an array storing all the links.
         */
        public Link[] getLinks() {
            return out_links.toArray(new Link[0]);
        }

        /**
         * Get the data in this node.
         *
         * @return the data.
         */
        public Object getData() {
            return data;
        }

        /**
         * Set the data in this node.
         *
         * @param data the new data;
         * @throws UnsupportedOperationException if the graph is fixed.
         */
        public void setData(Object data) {
            if (graph.fixed) {
                throw new UnsupportedOperationException();
            }

            this.data = data;
        }

        private void removeAllInLinks() {
            synchronized (graph) {
                assert graph.fixed == false;

                for (Link link : in_links) {
                    Node originNode = link.originNode;
                    originNode.out_links.remove(link);
                    link.graph = null;
                    link.originNode = null;
                    link.targetNode = null;
                }
                in_links.clear();
            }
        }
    }

    /**
     * A directional link which presents the relationship between the nodes in
     * the graph.
     */
    public static class Link {

        private Graph graph;
        private Node originNode;
        private Node targetNode;
        private Object data;

        private Link(Graph graph, Node originNode, Node targetNode) {
            this.graph = graph;
            this.originNode = originNode;
            this.targetNode = targetNode;
        }

        /**
         * Get the data stored in this link.
         *
         * @return the data.
         */
        public Object getData() {
            return data;
        }

        /**
         * Store the data in this link.
         *
         * @param data the new data.
         */
        public void setData(Object data) {
            if (graph.fixed) {
                throw new UnsupportedOperationException();
            }

            this.data = data;
        }

        /**
         * Get the origin node of this link.
         *
         * @return the origin node.
         */
        public Node getOrigin() {
            return originNode;
        }

        /**
         * Get the target node of this link.
         *
         * @return the target node.
         */
        public Node getTarget() {
            return targetNode;
        }
    }

    public static interface Handler {

        boolean judge(Object key, Node node, int link_index, Link link);
    }

    public static interface Listener {

        boolean move(Object originKey, Node originNode, int link_index, Link link);
    }
}